package com.cango.student.algorithm.nodepackage;

/**
 * 判断回环函数
 */
public class IsPalindrome {
    public static boolean isPalindrome(Node node) {

        if (node == null || node.next == null) {
            return true;
        }

        Node fast = node;
        Node slow = node;
        Node prev = null;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            // 临时node
            Node tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }

        // 对待奇数，slow向前一格
        if (fast != null && fast.next == null) {
            slow = slow.next;
        }

        while (slow != null) {
            if (slow.data != prev.data) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }

        return true;
    }

    public static void main(String[] args) {
//        Node linkNode1 = new Node();
//        linkNode1.data = 1;
//        Node linkNode2 = new Node();
//        linkNode2.data = 2;
//        Node linkNode3 = new Node();
//        linkNode3.data = 3;
//        Node linkNode4 = new Node();
//        linkNode4.data = 3;
//        Node linkNode5 = new Node();
//        linkNode5.data = 2;
//        Node linkNode6 = new Node();
//        linkNode6.data = 1;
//
//        linkNode1.next = linkNode2;
//        linkNode2.next = linkNode3;
//        linkNode3.next = linkNode4;
//        linkNode4.next = linkNode5;
//        linkNode5.next = linkNode6;


        Node linkNode1 = new Node();
        linkNode1.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 2;
        Node linkNode3 = new Node();
        linkNode3.data = 3;
        Node linkNode4 = new Node();
        linkNode4.data = 2;
        Node linkNode5 = new Node();
        linkNode5.data = 1;

        linkNode1.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;

//        Node linkNode1 = new Node();
//        linkNode1.data = 1;
//        Node linkNode2 = new Node();
//        linkNode2.data = 2;

        linkNode1.next = linkNode2;

        System.out.println(isPalindrome(linkNode1));

    }
}
